import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    //整数替换(递归)
    public static int integerReplacement1(int n) {
        int count = 0;
        if(n == 1) return 0;//递归出口
        if(n % 2 == 0){
            count += integerReplacement(n / 2);
        }else{
            count += Math.min(integerReplacement(n+1), integerReplacement(n-1));
        }
        count += 1;
        return count;
    }
    //整数替换(递归 + 记忆化搜索)
    static Map<Integer, Integer> hash = new HashMap<>();
    public static int integerReplacement(int n) {
        int count = 0;
        if(n == 1) return 0;//递归出口
        if(hash.containsKey(n)){
            count += hash.get(n);
        }else {
            if (n % 2 == 0) {
                count += integerReplacement(n / 2);
            } else {
                count += Math.min(integerReplacement(n + 1), integerReplacement(n - 1));
            }
            count += 1;
            hash.put(n, count);
        }
        return count;
    }
    //贪心(注意数据溢出)
    public static int integerReplacement2(int n) {
        if(n == 1){
            return 0;
        }
        int count = 0;
        while(n > 1){
            if(n % 2 == 0){
                n /= 2;
                count++;
            }else{
                if(n == 3){
                    count += 2;
                    n = 1;
                }else if(n % 4 == 1){
                    n /= 2;
                    count += 2;
                }else if(n % 4 == 3){
                    n = n / 2 + 1;
                    count += 2;
                }
            }
        }
        return count;
    }
    //可被三整除的最大和
    public static int maxSumDivThree(int[] nums) {
        int sum = 0;
        int x1 = (int)Math.pow(10, 5);
        int x2 = (int)Math.pow(10, 5);
        int y1 = (int)Math.pow(10, 5);
        int y2 = (int)Math.pow(10, 5);
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            if(nums[i] % 3 == 1){
                if(nums[i] % 3 == 1 && nums[i] < x1){
                    x2 = x1;
                    x1 = nums[i];
                }else if(nums[i] % 3 == 1 && nums[i] < x2){
                    x2 = nums[i];
                }
            }else if(nums[i] % 3 == 2){
                if(nums[i] % 3 == 2 && nums[i] < y1){
                    y2 = y1;
                    y1 = nums[i];
                }else if(nums[i] % 3 == 2 && nums[i] < y2){
                    y2 = nums[i];
                }
            }
        }
        if(sum % 3 == 0){
            return sum;
        }else if(sum % 3 == 1){
            if(x1 < sum && y1 + y2 < sum){
                sum -= Math.min(x1, y1 + y2);
            }else if(x1 < sum){
                sum -= x1;
            }else if(y1 + y2 < sum){
                sum -= (y1 + y2);
            }else{
                return 0;
            }

        }else if(sum % 3 == 2){
            if(x1 + x2 < sum && y1 < sum){
                sum -= Math.min(x1 + x2, y1);
            }else if(x1 + x2 < sum){
                sum -= x1 + x2;
            }else if(y1 < sum){
                sum -= y1;
            }else{
                return 0;
            }
        }
        return sum;
    }
    //距离相等的条形码
    public static int[] rearrangeBarcodes(int[] barcodes) {
        int len = barcodes.length;
        int[] ret = new int[len];
        Map<Integer, Integer> hash = new HashMap<>();
        int maxValue = barcodes[0];
        int maxCount = 1;
        for(int k : barcodes){
            hash.put(k, hash.getOrDefault(k, 0) + 1);
            if(hash.get(k) > maxCount){
                maxValue = k;
                maxCount = hash.get(k);
            }
        }
        //先处理出现次数最多的数
        int index = 0;
        for(int i = 0; i < maxCount; i++){
            ret[index] = maxValue;
            index += 2;
        }
        hash.remove(maxValue);
        //处理其他数
        for(int x: hash.keySet()){
            int count = hash.get(x);
            for(int i = 0; i < count; i++){
                if(index >= len) index = 1;
                ret[index] = x;
                index += 2;
            }
        }
        return ret;
    }
    //重构字符串
    public String reorganizeString(String s) {
        char[] chs = s.toCharArray();
        int len = chs.length;
        Map<Character, Integer> hash = new HashMap<>();
        char maxValue = chs[0];
        int maxCount = 1;
        for(int i = 0; i < len; i++){
            hash.put(chs[i], hash.getOrDefault(chs[i], 0) + 1);
            if(hash.get(chs[i]) > maxCount){
                maxValue = chs[i];
                maxCount = hash.get(chs[i]);
            }
        }
        if(maxCount > (len + 1) / 2) return "";
        char[] ret = new char[len];
        int index = 0;
        for(int i = 0; i < maxCount; i++){
            ret[index] = maxValue;
            index += 2;
        }
        hash.remove(maxValue);
        for(char ch : hash.keySet()){
            int count = hash.get(ch);
            for(int i = 0; i < count; i++){
                if(index >= len) index = 1;
                ret[index] = ch;
                index += 2;
            }
        }
        return new String(ret);
    }
    //俄罗斯套娃问题
    public static int maxEnvelopes(int[][] envelopes) {
        //重写排序
        Arrays.sort(envelopes, (a, b) ->{
            if(a[0] < b[0]){
                return -1;
            }else if(a[0] > b[0]){
                return 1;
            }else{
                if(a[1] < b[1]){
                    return 1;
                }else if(a[1] > b[1]){
                    return -1;
                }else{
                    return 0;
                }
            }
        });
        int len = envelopes.length;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(envelopes[0][1]);
        for(int i = 1; i < len; i++){
            int y = envelopes[i][1];
            if(y > list.get(list.size() - 1)){
                list.add(y);
            }else{
                int left = 0, right = list.size() - 1;
                while(left < right){
                    int mid = (left + right) / 2;
                    if(list.get(mid) >= y) right = mid;
                    else left = mid + 1;
                }
                list.set(left, y);
            }
        }
        return list.size();
    }

    public static void main(String[] args) {
      //  integerReplacement2(2147483647);
        int[] nums = {1,1,1,1,2,2,3,3};
        int[][] arr = {{2,100},{3,200},{4,300},{5,500},{5,400},{5,250},{6,370},{6,360},{7,380}};
        maxEnvelopes(arr);
        rearrangeBarcodes(nums);
        maxSumDivThree(nums);

    }

}